#include <cstdio>
#include <unordered_set>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
/*
 * @lc app=leetcode.cn id=160 lang=cpp
 *
 * [160] 相交链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // HashSet笨蛋方法
    // ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    //     unordered_set<ListNode*> record;
    //     while (headA) {
    //         record.insert(headA);
    //         headA = headA->next;
    //     }
    //     while (headB) {
    //         if (record.count(headB)) return headB;
    //         headB = headB->next;
    //     }
    //     return nullptr;

    // }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *l = headA, *r = headB;
        while (l != r) {
            l = l ? l->next : headA;
            r = r ? r->next : headB;
        } 
        return l;
    }
};
// @lc code=end

